Codeforces Round #216 (Div. 2)

A

讨论对于每一天吃饭需不需要洗餐具即可，优先使用盘子，其次使用碗，都没有就洗一个。

时间复杂度 $O(n)$ 。

Code

#include <bits/stdc++.h>
using namespace std;

const int N = 1005;

int n, m, k, ans, a[N];

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) {
        if (a[i] == 1) m ? m-- : ans++;
        if (a[i] == 2) k ? k-- : m ? m-- : ans++;
    }
    cout << ans << endl;
}

B

按照 $a_1\ge a_2\ge\cdots\ge a_n$ 的顺序安排，先求出 $\sum\limits_{i=k+1}^n a_i$ 并安排 $[k+1,\,n]$ ，然后再安排 $[1,\,k]$ 即可。

时间复杂度 $O(n)$ ，注意 $n=k$ 的特殊情况。

Code

#include <bits/stdc++.h>
using namespace std;

const int N = 1005;

int n, k, l, r, S_all, S_k;
int a[N], S_res;

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> k >> l >> r >> S_all >> S_k;
    if (n != k) {
        S_res = S_all - S_k;
        for (int i = k + 1; i <= n; i++) a[i] = l;
        S_res -= (n - k) * l;
        for (int i = k + 1; i <= n; i++) a[i] += S_res / (n - k);
        S_res %= (n - k);
        for (int i = k + 1; i <= k + S_res; i++) a[i]++;
        for (int i = 1; i <= k; i++) a[i] = a[k + 1];
        S_k -= k * a[k + 1];
        for (int i = 1; i <= k; i++) a[i] += S_k / k;
        S_k %= k;
        for (int i = 1; i <= S_k; i++) a[i]++;
    } else {
        for (int i = 1; i <= n; i++) a[i] = S_all / n;
        S_all %= n;
        for (int i = 1; i <= S_all; i++) a[i]++;
    }
    for (int i = 1; i <= n; i++) cout << a[i] << " \n"[i == n];
}

C

维护一个答案集合 $S$ ，在搜索过程中维护修复根结点到 $u$ 路径上所有问题边所需要选中的结点 $x$，如果边 $(u,v)$ 为问题边则将 $x$ 从 $S$ 中删除并加入 $v$ 。

时间复杂度 $O(n\log{n})$ 。

Code

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;

struct edge {
    int v, next, w;
    edge(): v(0), next(0), w(0) {}
    edge(int v, int next, int w): v(v), next(next), w(w) {}
} e[N];

int p[N], dep[N], n, eid;
set<int> st;

inline void insert(int u, int v, int w) {
    e[eid] = edge(v, p[u], w);
    p[u] = eid++;
}

void dfs(int u, int fa, int mn) {
    for (int i = p[u]; i != -1; i = e[i].next) {
        int v = e[i].v;
        if (v == fa) continue;
        if (e[i].w) {
            st.erase(mn);
            st.insert(v);
            dfs(v, u, v);
        }
        else dfs(v, u, mn);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    memset(p, -1, sizeof(p));
    for (int i = 1; i <= n - 1; i++) {
        int u, v, t;
        cin >> u >> v >> t;
        t--;
        insert(u, v, t);
        insert(v, u, t);
    }
    dfs(1, 1, 1);
    cout << st.size() << endl;
    for (int it : st) cout << it << " ";
}

D

注意到局面的改变只与编号最小的两个人有关，考虑dp。设 $f_{i,j}$ 为幸存者编号最小值为 $i$ ，次小值为 $j$ 的局面出现的最小轮数。

由于需要快速判断 $i$ 是否有可能被后面的人打死，考虑维护 $p$ 的后缀最大值 $suf_i=\max\limits_{j=i}^n p_i$ ，讨论最大值和最小值的更新方法，从而得到转移方程：

• 若 $i$ 被打死且 $j$ 存活，需要满足 $p_i<1$ 且 $suf_j>0$ ，此时有转移

$f_{j,j+1}=\min\{f_{j,j+1},\,f_{i,j}+1\}$

• 若 $i$ 打死 $j$ 且 $i$ 存活，需要满足 $suf_j<1$ 且 $p_i>0$ ，此时有转移

$f_{i,j+1}=\min\{f_{i,j+1},\,f_{i,j}+1\}$

• 若 $i$ 和 $j$ 都被打死，需要满足 $suf_j>0$ 且 $p_i>0$ ，此时有转移

$f_{j+1,j+2}=\min\{f_{j+1,j+2},\,f_{i,j}+1\}$

最后统计所有情况中最小轮数小于等于 $k$ 的即可，时间复杂度 $O(n^2)$ 。

Code

#include <bits/stdc++.h>
using namespace std;

const int N = 3005;

int f[N][N], p[N], suf[N], n, k, ans;

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> p[i];
    memset(f, 0x3f, sizeof(f));
    for (int i = n; i >= 1; i--) suf[i] = max(suf[i + 1], p[i]);
    f[1][2] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            int v = f[i][j] + 1;
            if (suf[j] && p[i] != 100) f[j][j + 1] = min(f[j][j + 1], v);
            if (suf[j] && p[i]) f[j + 1][j + 2] = min(f[j + 1][j + 2], v);
            if (suf[j] != 100 && p[i]) f[i][j + 1] = min(f[i][j + 1], v);
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n + 1; j++)
            ans += (f[i][j] <= k);
    }
    cout << ans + (f[n + 1][n + 2] <= k) << endl;
}

E

待补。